![]() |
The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson Wiley Computer Publishing, John Wiley & Sons, Inc. ISBN: 0471353817 Pub Date: 03/01/99 |
Previous | Table of Contents | Next |
An attacker who has control of the XOR difference sequences in Ai, Bi does not necessarily have great control over the XOR or modulo 232 difference sequence that appears in the subkeys.
First, we must consider the context of a related-key differential attack. The attacker does not generally know all of the key bytes generating either Ai or Bi. Instead, he knows the XOR difference sequence in Ai and Bi.
Consider an Ai value with an XOR difference of δ. If the Hamming weight of δ is k, not including the high-order bit, then the best estimate for the XOR difference that ends up in the two subkey words for a given round generally has probability of about 2-2k. (Control of the Ai, Bi XOR difference sequence does not make controlling the subkey XOR differences substantially easier.)
Consider an Ai value with an XOR difference of δ. If the Hamming weight of δ is k, then the best estimate for the modulo 232 difference of the two subkey words for a given round has probability of about 2-k.
This points out one of the difficulties in mounting any kind of successful related-key attack with non-zero Ai, Bi difference sequences. If an attacker can find a difference sequence for Ai, Bi that keeps k = 3, and needs to control the subkey differences for 12 rounds, he has a probability of about 2-72 of getting the most likely XOR subkey difference sequence, and about 2-36 of getting the most likely modulo 232 difference sequence. After getting the most likely mod 232 difference into the subkeys, however, the attacker must deal with the fact that the output values are XORed into half of the block. Those relatively high-probability mod 232 differences end up back at 2-72 probability for any given XOR difference sequence actually being XORed into the successive rounds target blocks.
We consider the use of the RS matrix in deriving S from M to be a powerful defense against related-key differential attacks, because it forces an attacker to keep at least five key generation S-boxes active. Our analysis suggests that any useful control of the subkey difference sequence requires that each active S-box in the attack have all four key bytes changed.
Further, our analysis suggests that, for nearly any useful difference sequence, each active S-box in the attack has a specific pair of defining key bytes it needs to work. An attacker specifying his key relation in terms of bytewise XOR has five pairs of sequences of four key bytes each, which he wants to get. This leaves him with a probability of a pair of keys with his desired relation actually leading to the desired attack of about 2-115, which moves the attack totally outside the realm of practical attacks.
So long as an attacker is unable to improve this, either by finding a way to get useful difference sequences into the subkeys without having so many active key bytes, or by finding a way to mount related-key attacks with different S values for the different keys, we do not believe that any kind of related-key differential attack is feasible.
Note the implication of this: clever ways to control a couple extra rounds subkey differences are not going to make the attacks feasible, unless they also allow the attacker to use far fewer active key bytes. For reference, note that with one altered key byte per active subkey generation S-box, the attacker ends up with a 2-39 probability that a pair of related keys will yield an attack; with two key bytes per active S-box, this increases to 2-78; with three key bytes per active S-box, it increases to 2-117. In practice, this means that any key relation requiring more than one byte of key changed per active S-box appears to be impractical.
Our analysis suggests that related-key differential attacks against the full Twofish are not workable. Note, however, that we have spent less time working on resistance to chosen-key attacks, such as will be available to an attacker if Twofish is used in the straightforward way to define a hash function. For this reason, we recommend that more analysis be done before Twofish is used in the straightforward way as a hash function, and we note that it appears to be much more secure to use Twofish in this way with 128-bit keys than with 256-bit keys, despite the fact that this also slows the speed of a hash function down by a factor of two.
A chosen-key attack is a variant of a related-key attack. Not only are there several keys that are related, the attacker actually gets to choose some parts of these keys. The parts not chosen are unknown to the attacker, and the objective of the attack is to find them.
Attack Type | Rounds | Work Factor | Text Req. | Special Req. |
---|
Partial Chosen Key | 10 | 234 | 232;212 | 160 bits of key from K, K* chosen by attacker |
Related-Key | 10 | 2187 | 232;212 | 2155 related-key queries |
Table 9.9. Attack Results for Our Chosen-key Attack |
Results. We define a partial chosen key attack on a 10-round Twofish without the pre- or post-whitening. The attack requires us to control 20 selected bytes of the key, and to set them differently for a pair of related keys K, K*. The remaining 12 bytes of the two keys, which are the same for both keys, are unknown to us; recovering them is the objective of the attack. Our attack results are summarized in Table 9.9.
Note that the text requirements are shown as n;m, where n is the number of chosen plaintexts, and m is the number of adaptive chosen plaintexts. Also note that the related-key version of the attack requires this many chosen and adaptive chosen plaintexts for each of the 2155 related-key pairs.
How the Attack Works. The attack works as follows:
The first step in the attack is finding a pair of keys, K, K*, with some relationship, such that we get a useful subkey difference sequence, while leaving the S key unchanged. We described above how such keys can exist. Here, we assume the existence of some pair of keys with a subkey XOR difference sequence zero in rounds one through eight but with non-zero XOR subkey differences in rounds zero and nine.
Structure of the Key Pair. Based on the discussion above, we assume that the keys K, K* differ in 20 bytes, with the changed bytes selected in such a way to leave S unchanged between the two keys, and to change all four key bytes used to define five of the S-boxes used for subkey generation. We note that a random pair of keys chosen to have this property has only a 2-155 probability of being the pair of keys that will generate our desired sub-key difference sequence. This makes this attack impractical as a differential related-key attack, though an attacker who is able to control the active 20 bytes of key involved in a pair of keys could mount the attack for a chosen pair of keys. (That is, the attacker could choose the values of the active 20 bytes of both K and K*, while remaining ignorant of the other twelve bytes of K and K*, which must be identical for both keys. The attacker would then attempt to learn those remaining 12 bytes of key.)
Subkey Differences. We actually care only about the subkey difference in the round subkey words. Recall that the subkey words are generated from a pair of 32-bit words, which are generated from the subkey generation S-boxes. Lets call these values U, V and U*, V*. We dont know any of U, V, U*, V*, but we do know U′ = U ⊕ U* and V′ = V ′ V*.
Previous | Table of Contents | Next |